package com.arron.algorithm.leetcodetop100.动态规划;


/**
 * 509. 斐波那契数
 */
public class Fib {

    /**
     * 迭代
     * @param n
     * @return
     */
    public int fib(int n) {
        if(n<2){
            if(n==0) {
                return 0;
            }
            if(n==1) {
                return 1;
            }
        }
        int[] res = new int[n+1];
        res[0] = 0;
        res[1] = 1;
        for(int i= 2;i<res.length;i++){
            res[i] = res[i-1]+res[i-2];
        }
        return res[n];
    }

    /**
     * 优化空间复杂度
     * @param n
     * @return
     */
    public int fib_plus(int n) {
        if(n<2){
            if(n==0) {
                return 0;
            }
            if(n==1) {
                return 1;
            }
        }

        int dp_1 = 0;
        int dp_2 = 1;
        int dp =0;
        for(int i= 2;i<=n;i++){
            dp = dp_1+dp_2;
            dp_1=dp_2;
            dp_2 = dp;

        }
        return dp;
    }

    public int fib_dfs(int n) {
       if (n==1 || n==0){
           return n;
       }
        return fib_dfs(n-1)+fib_dfs(n-2);
    }

    /**
     * 带记忆的递归
     * @param n
     * @return
     */
    public int fib_dfs_plus(int n,int[] dp) {
        if (n==1 || n==0){
            return n;
        }
        if (dp[n]!=0){
            return dp[n];
        }
        dp[n] = fib_dfs_plus(n-1,dp)+fib_dfs_plus(n-2,dp);

        return dp[n];
    }




    public static void main(String[] args) {
        Fib fib = new Fib();
        long l = System.currentTimeMillis();
        System.out.println(fib.fib(40));
        System.out.println(System.currentTimeMillis()-l);
    }
}
